class Solution {
public:
//     int Fibonacci(int n) {
//         if(n == 0 || n == 1) return n;
//         return Fibonacci(n-1) + Fibonacci(n-2);
//     }
    
//     int Fibonacci(int n) {
//         if(n == 0 || n == 1) return n;
//         vector<int> v(n+1, 0);
//         v[1] = v[2] = 1;
//         for(int i = 2; i <= n; ++i) {
//             v[i] = v[i-1] + v[i-2];
//         }
//         return v[n];
//     }
    int Fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        int a = 0;
        int b = 1;
        int ans = 0;
        for(int i = 2; i <= n; ++i) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return ans;
    }
};